VfB Stuttgart

Khedira memulakan kerjayanya di peringkat belia di TV Oeffingen sebelum berpindah ke VfB Stuttgart pada tahun 2005, setahun sebelum abangnya, Sami, menyertai.[2][3] Selepas menapak di akademi Stuttgart, beliau mula bermain untuk pasukan U16 pada tahun 2009.[4] Beliau menandatangani kontrak dengan kelab tersebut, menyimpannya sehingga 2013.[5] Pada 28 Januari 2012, Khedira membuat penampilan pertamanya untuk VfB Stuttgart II dalam Liga 3 menentang FC Rot-Weiß Erfurt.[6] Semasa di pasukan simpanan VfB Stuttgart, beliau menjaringkan sekali untuk pasukan itu, dalam kemenangan 4–0 menentang Wacker Burghausen pada 8 September 2013.[7]

Pada 23 Oktober 2012, Khedira dipromosikan ke pasukan utama VfB Stuttgart.[8] Beliau melanjutkan kontrak dengan kelab pada 28 Januari 2013 sehingga Jun 2015.[9] Walau bagaimanapun, sepanjang musim 2012–13, Khedira tidak pernah membuat penampilan pertama dalam pasukan utama, kerana kebanyakannya muncul sebagai pemain simpanan yang tidak digunakan.[10]

Pada 1 September 2013, Khedira membuat penampilan pertama dalam Bundesliga untuk VfB Stuttgart dalam kemenangan 6–2 di rumah menentang 1899 Hoffenheim.[11] Pada 7 Disember 2013, beliau membuat penampilan pertama sebagai pemain mula untuk Stuttgart, dalam kemenangan 4–2 menentang Hannover 96.[12] Dari 29 Januari 2014 hingga 2 Mac 2014, beliau mendapat beberapa peluang untuk menjadi pemain mula dalam pasukan utama.[13] Walaupun beliau kemudian kehilangan tempat dalam pasukan utama, Khedira terus membuat sembilan penampilan untuk kelab tersebut.

RB Leipzig

Untuk musim 2014–15, Khedira berpindah ke RB Leipzig, menandatangani kontrak tiga tahun, menyimpannya sehingga 2017.[14] Perpindahan itu dilaporkan tidak didedahkan.[15] RB Leipzig telah berminat untuk menandatangani beliau sejak September 2013.[16]

Khedira membuat penampilan pertama bagi RB Leipzig dalam perlawanan pembuka musim, bermain sepanjang perlawanan, dalam seri 0–0 menentang VfR Aalen.[17] Selepas membuat penampilan pertamanya bagi RB Leipzig, beliau dengan cepat menetapkan dirinya dalam pasukan utama dan memainkan peranan penting bagi kelab dalam musim pertamanya.[18] Beliau juga menjadi pemain mula tetap sejak awal musim sehingga dia digantung satu perlawanan menentang SV Sandhausen pada 30 November 2014 kerana telah mendapat lima kad kuning dalam musim ini.[19] Walau bagaimanapun, dalam kekalahan 1–0 menentang FSV Frankfurt pada 15 Februari 2015, beliau mengalami kecederaan kaki pada minit ke-69 dan digantikan sebagai akibatnya.[20] Kecederaan itu menyebabkannya keluar dari aksi untuk beberapa minggu.[21] Pada 17 Mei 2015, beliau kembali ke pasukan utama selepas kecederaan, dalam kekalahan 2–1 menentang Ingolstadt.[22] Dalam musim pertamanya di kelab, Khedira membuat 24 penampilan dalam semua pertandingan.

Pada musim kedua di RB Leipzig, Khedira mendapati dirinya dalam pertandingan untuk posisinya dan ini mengakibatkan beliau duduk di bangku simpanan pada permulaan musim.[23] Kemudian dalam musim itu, beliau diganggu oleh kecederaan.[24][25] Walaupun begitu, beliau terus membuat 16 penampilan dalam semua pertandingan, ketika RB Leipzig dipromosikan ke Bundesliga.

Menjelang musim 2016–17, peluang pertama Khedira dalam pasukan terus terhad dan beliau kekal di bangku simpanan susulan pertandingan baru dan pada bulan November, beliau belum membuat penampilan pertamanya untuk musim tersebut.[26] Pada 25 November 2016, beliau membuat penampilan pertamanya untuk musim 2016–17, masuk sebagai pemain gantian pada separuh masa kedua, dalam kemenangan 4–1 menentang Freiburg.[27] Beliau kemudian membuat sepuluh penampilan untuk kelab musim ini. Walau bagaimanapun, diumumkan bahawa Khedira dilepaskan oleh kelab.[28] Beliau sebelum ini telah dinasihatkan oleh abangnya untuk tidak meninggalkan kelab.[29]

FC Augsburg

Dengan kontraknya di RB Leipzig yang tamat pada akhir musim 2016–17, Khedira menyertai kelab Bundesliga yang lain, iaitu FC Augsburg pada 7 Jun 2017, dengan menandatangani kontrak selama empat tahun.[30]

Union Berlin

Pada April 2021, diumumkan bahawa Khedira akan menyertai Union Berlin bermula dari musim 2021–22.[31] Pada 19 Mac 2023, beliau mencipta gol pertamanya di kelab tersebut dalam kemenangan 2–0 menentang Eintracht Frankfurt.[32] Pada hari terakhir musim 2022–23, beliau menjaringkan gol tunggal dalam kemenangan 1–0 menentang Werder Bremen, untuk menjamin tempat keempat bagi kelabnya dalam liga dan kelayakan ke Liga Juara-Juara musim seterusnya.[33]